#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<vector>
#include<bitset>
#include<iostream>
using namespace std;
//BKDR算法
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template<size_t N,	////非类型模板参数,共插入多少个值
size_t X = 4,	//X值越大,产生冲突的概率越低, N*X表示位图开辟多少个比特位空间
class K = string,// 假设布隆过滤器中元素类型为K,默认为string类型
//每个元素对应3个哈希函数
class HashFunc1 = BKDRHash,//一个字符串想映射几个比特位就给几个HashFunc仿函数计算哈希地址
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	//将key所在的三个映射位设为1
	void Set(const K& key)
	{
		size_t len = N * X;//总长度 
		//计算映射的哈希地址 HashFunc()是匿名对象
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;

		//将对应的映射位置标志为1
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	//判断key是否在布隆过滤器中
	bool Test(const K& key)
	{
		//三个映射为都是1才在(可能存在误判),其中一个不是1就不在
		size_t len = N * X;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
 		if ( (!_bs.test(index1)) || (!_bs.test(index2)) || (!_bs.test(index3)))
		{
			return false;
		}
		return true;//可能存在误判	
	}
// 不支持删除,删除可能会影响其他值,
// 一般情况不支持删除,why?->多个值可能会标记一个位,删除可能会影响其他key
// 如果非要支持删除的话,标记不再使用一个比特位,可以使用多个比特位,进行计数多少个值映射的这个比特位
// 但是这种方法是杀敌一千,自损八百的做法,因为消耗的更多的空间
	void Reset(const K& key);
private:
    //此时k为3 则此时位图的大小大致应该为: m = 4.2*n 即X = 4
	bitset<N*X> _bs;
};
